# 全排列算法
from typing import List


def permutation(l, level=0):
    # 如果当前层级等于列表长度，即达到最后一个位置，输出结果
    if level == len(l):
        print(l)
    else:
        # 遍历当前层级到最后一个位置的元素
        for i in range(level, len(l)):
            # 交换当前层级与遍历到的位置的元素
            l[level], l[i] = l[i], l[level]
            # 递归调用全排列算法，层级加1
            permutation(l, level + 1)
            # 恢复交换前的顺序，进行下一次交换
            l[level], l[i] = l[i], l[level]


# 二分查找算法
def binary_search(l: List[int], target: int) -> int:
    left, right = 0, len(l) - 1
    while left <= right:
        mid = (left + right) // 2
        if l[mid] == target:
            return mid
        elif l[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


# 二分查找算法的递归实现
def binary_search_recursive(l: List[int], target: int, left: int, right: int) -> int:
    if left > right:
        return -1
    mid = (left + right) // 2
    if l[mid] == target:
        return mid
    elif l[mid] < target:
        return binary_search_recursive(l, target, mid + 1, right)
    else:
        return binary_search_recursive(l, target, left, mid - 1)


if __name__ == "__main__":
    l = "abc"
    l = list(l)
    permutation(l)
